/**
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。 

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

 

示例 1：

输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]
示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
*/

class Solution {
    List<List<Integer>> res=new ArrayList();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        if(candidates.length==0) return res;
        int max=Math.max(target/candidates[0],candidates.length);
        boolean[] visited=new boolean[candidates.length];
        for(int i=1;i<=max;i++){
            dfs(i,0,0,target,candidates,visited,new ArrayList());
        }
        return res;
    }
    public void dfs(int n,int start,int sum,int target,int[] candidates,boolean[] visited,List<Integer> path){
        if(sum>target){
            return;
        }
        if(n==path.size()){
            if(sum==target){
                res.add(new ArrayList(path));
            }
            return;
        }
        for(int i=start;i<candidates.length;i++){
            if(i>start&&candidates[i]==candidates[i-1] && !visited[i]){
                continue;
            }
            path.add(candidates[i]);
            sum=sum+candidates[i];
            visited[i]=true;
            dfs(n,i,sum,target,candidates,visited,path);//又把i写成start了 ，我真是傻了
            sum=sum-candidates[i];
            path.remove(path.size()-1);
            visited[i]=false;
        }
    }
}